package src.array;

import java.util.Arrays;
import java.util.HashMap;

public class no1365 {
    //有多少小于当前数字的数字
    public static void main(String[] args) {
        int[] arr = {8, 1, 2, 2, 3};
        int[] res = smallerNumbersThanCurrent1(arr);
        System.out.println(Arrays.toString(res));  //返回[4,0,1,1,3]

    }

    public static int[] smallerNumbersThanCurrent1(int[] nums) {
        int max = Arrays.stream(nums).max().getAsInt();  //记住这个方法，求数组最值平均值
        int[] hashArray = new int[max + 1];
        int[] copyArray = Arrays.copyOf(nums, nums.length);
        Arrays.sort(nums);

        for (int i = nums.length - 1; i >= 0; i--) {  //从右往左遍历
            hashArray[nums[i]] = i;
        }

        int[] res = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            res[i] = hashArray[copyArray[i]];
        }

        return res;

    }

    public static int[] smallerNumbersThanCurrent2(int[] nums) {
        //最关键的一点：先排序，排序之后，元素下标就是小于当前数字的个数
        //当有连续几个连续重复数字时，就看第一次出现的下标，比如[1,2,2,3,8]，就看第一个2的下标，因此可以从右往左遍历原数组来构建hash数组
        int[] copyArray = Arrays.copyOf(nums, nums.length);  //排序后nums[]就打乱了，所以先复制一份
        Arrays.sort(nums);
        HashMap<Integer, Integer> map = new HashMap<>();  //K存数字，V存次数，也就是下标
        for (int i = 0; i < nums.length; i++) {
            if (!map.containsKey(nums[i])) {
                map.put(nums[i], i);
            }
        }
        int[] res = new int[nums.length];
        for (int i = 0; i < copyArray.length; i++) {
            if (map.containsKey(copyArray[i])) {
                res[i] = map.get(copyArray[i]);
            }
        }
        return res;
    }
}
